﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Emil.GMP;

namespace ProjectEulerSolutions.Problems
{
    /*
     * 

Consider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + ..., where Gk is the kth term of the second order recurrence relation Gk = Gk−1 + Gk−2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, ... .

For this problem we shall be concerned with values of x for which AG(x) is a positive integer.

The corresponding values of x for the first five natural numbers are shown below.
x	AG(x)
(√5−1)/4	1
2/5	2
(√22−2)/6	3
(√137−5)/14	4
1/2	5

We shall call AG(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 20th golden nugget is 211345365.

Find the sum of the first thirty golden nuggets.

     * */
    class Problem140 : IProblem
    {
        public string Calculate()
        {
            //Ag(x) = (x + 3x^2) / (1 - x - x^2)

            long n = 0;
            int count = 0;
            int target = 30;

            long sum = 0;

            while (count < target)
            {
                n++;

                BigInt bigN = new BigInt(n.ToString());
                BigInt bigTemp = 5 * bigN * bigN + 14 * bigN + 1;

                if (bigTemp.IsPerfectSquare())
                {
                    count++;

                    sum += n;
                    Console.WriteLine("{0}: {1} - {2}", count, n, bigTemp);
                    if (count < target)
                    {
                        if (count % 2 == 1)
                        {
                            n = (long)(n * 1.9387489019);
                        }
                        else
                        {
                            n = (long)(n * 3.535322165);
                        }

                        //preskočimo brojeve (jer je testiranje pokazalo da je svaki četvrti racionalan...
                        //iako bi mogo i sve to odjebat i samo računat fibonnacie ali kgj ionako je samo 13 ms
                        //double phi = (Math.Sqrt(5) + 1) / 2;
                        //double ratio = Math.Pow(phi, 1);
                        //n = (long)(n * ratio);
                    }
                }
            }
            return sum.ToString();
        }
    }
}
